// covertree.cpp
// 04/17/2011: created

#include "covertree.h"
#include <QtCore/QVector>
#include "Log.h"

#define for_all_node_data(i) for (int i = 0; i < n(); i++)

CoverTree::CoverTree(dataset_type& data)
  : Tree(data)
{
}

CoverTree::CoverTree(CoverTree* parent, int s, int e, double radius, bool only_child)
  : Tree(parent, s, e), m_radius(radius), m_only_child(only_child)
{
}

CoverTree::~CoverTree()
{
  if (!m_parent) {
  }
}

#define for_all_node_data_from(i, j) for (int j = i; j < n(); j++)

int CoverTree::split()
{
  // first, try with radius-1
  int n_left = 0;
  double r = pow(2, m_radius-1);
  for_all_node_data(i) if (distance(0, i) <= r) {
    swap(n_left, i);
    n_left++;
  }

  if (n_left == n()) {  // all points are covered
    if (m_only_child) {
      m_radius--;       // implicit cover tree, no more only child node creation
//      Log::m_log << "implicit only child" << " m_s=" << m_s << " m_e=" << m_e << " r=" << m_radius << " n=" << n() << endl;
    }
    else {
      CoverTree *child = new CoverTree(this, m_s, m_e, m_radius-1, true);
      m_child.push_back(child);
//      Log::m_log << "create only child" << " m_s=" << child->m_s << " m_e=" << child->m_e << " r=" << child->m_radius << " n=" << child->n() << endl;
    }
  }
  else {
    CoverTree *child = new CoverTree(this, m_s, m_s+n_left, m_radius-1, true);
    m_child.push_back(child);
//    Log::m_log << "create child" << " m_s=" << child->m_s << " m_e=" << child->m_e << " r=" << child->m_radius << " n=" << child->n() << endl;
    while (n_left < n()) {
      int newCenter = n_left;
      double centerIdx = rand() % (n()-newCenter) + newCenter;
      swap(newCenter, centerIdx);                     // choose a new center from the rest of the points
      for_all_node_data_from(newCenter, i) if (distance(newCenter, i) <= r) {
        swap(n_left, i);
        n_left++;
      }
      CoverTree *child = new CoverTree(this, m_s+newCenter, m_s+n_left, m_radius-1, false);
      m_child.push_back(child);
//      Log::m_log << "create child" << " m_s=" << child->m_s << " m_e=" << child->m_e << " r=" << child->m_radius << " n=" << child->n() << endl;
    }
  }
  return n_left;
}

void CoverTree::buildTree()
{
  if (!m_parent) {
    int rootIdx = rand() % n();
    swap(rootIdx, 0);
    double max_dist = 0;
    for_all_node_data(i) {
      double dist = distance(0, i);
      if (dist > max_dist) max_dist = dist;
    }
    m_radius = floor(log(max_dist) / log(2.0))+1;
    m_only_child = true;
//    Log::m_log << "root radius=" << m_radius << endl;
  }

  int n_left = -1;

  if (n() > 10) {  // only split big nodes
    n_left = split();
  }

  for (unsigned int i = 0; i < m_child.size(); i++)
    static_cast<CoverTree*>(m_child[i])->buildTree();
}

void CoverTree::findKNN(const vec& query, std::vector<int>& knnIdx, std::vector<double>& minBound, double radius)
{
  if (radius == POSITIVE_INFINITY) radius = m_radius;
  double lowerBound = arma::norm(query-get(0),2) - pow(2, radius);
//  Log::m_log << "lowerBound=" << lowerBound << endl;
  if (lowerBound >= minBound.back()) {               // pruned this node
//    Log::m_log << "pruned" << endl;
    return;
  }

  if (m_child.size() == 0) {
    Tree::findKNN(query, knnIdx, minBound);
  }
  else {
    if (radius > m_radius)  // an implicit only child
      this->findKNN(query, knnIdx, minBound, radius-1);
    else
      for (unsigned int i = 0; i < m_child.size(); i++) {
        CoverTree* child = static_cast<CoverTree*>(m_child[i]);
        child->findKNN(query, knnIdx, minBound, radius-1);
      }
  }
}

